package BackTracking;

/**
 * m图着色问题
 *
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2020/12/25 20:19
 */
public class GraphColoring {
    public static void main(String[] args) {
        backtrack(1);
    }

    static int n = 5;//图块数
    static int m = 4;//颜色数
    static int sum = 0;//记录解树模
    static int[][] G = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}};//相邻
    static int[] x = new int[n + 1];//解空间

    /**
     *  解空间：满m叉树
     *  约束条件：和已经确定颜色且有边相的顶点颜色不相同。
     *  限界条件：无
     * @param t
     */
    private static void backtrack(int t) {
        if (t > n) {
            sum++;
            System.out.println("第" + sum + "中种着色方案");
            for (int i = 1; i <= n; i++) {
                System.out.print(x[i]);
            }
            System.out.println();
        } else {
            for (int i = 1; i <= m; i++) {
                x[t] = i;
                if (OK(t)) {
                    backtrack(t + 1); //能着x[t]号色 递归
                }
            }
        }


    }

    /**
     * 判断当前着色是否成立
     * @param t
     * @return
     */
    private static boolean OK(int t) {
        for (int i = 0; i < G.length; i++) {
            if (G[i][1] == t) {
                if (x[t] == x[G[i][0]]) return false;
            } else if (G[i][0] == t) {
                if (x[t] == x[G[i][1]]) return false;
            }
        }
        return true;
    }

}
